#!/usr/bin/env python3

def quick_sort(seq, start, end):
    if start < end:
        i, j = start, end
        pivot = seq[start]
        while i < j:
            while (i < j) and (seq[j] >= pivot):
                j -= 1
            if i < j:
                seq[i] = seq[j]
                i += 1
            while (i < j) and (seq[i] <= pivot):
                i += 1
            if i < j:
                seq[j] = seq[i]
                j -= 1
        seq[i] = pivot
        quick_sort(seq, start, i - 1)
        quick_sort(seq, i + 1, end)

if __name__ == '__main__':
    seq = [72,6,57,88,60,42,83,73,48,85]
    print('Origin seq:', seq)
    quick_sort(seq, 0, len(seq)-1)
    print('Sorted seq:', seq)
    print('OK!' if seq == sorted(seq) else 'Wrong!!!')
